3. Longest Substring Without Repeating Characters

\3. Longest Substring Without Repeating Characters

Medium

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

1. 改良法

   使用res 变量来记录最终答案 而不是一个list，节省空间

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        res = 0
        mem = []
        for ch in s:
            if ch not in mem:
                mem.append(ch)
            else:
                res = max(res, len(mem))
                mem = mem[mem.index(ch)+1:]
                mem.append(ch)
        return max(res, len(mem))

2. 使用字典

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        ans = 0
        start = 0
        mem = {}
        for i, c in enumerate(s):
            if c in mem.keys():
                start = max(start, mem[c] + 1)
                
            mem[c] = i
            ans = max(ans, i-start+1)
        return ans